Drawing graphs.html (1696B)
1 <?xml version="1.0" encoding="UTF-8"?> 2 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> 3 <html><head><link rel="stylesheet" type="text/css" href="sitewide.css"><meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/><meta name="exporter-version" content="Evernote Mac 7.1.1 (456663)"/><meta name="keywords" content="ng"/><meta name="altitude" content="-1.767048716545105"/><meta name="author" content="Alex Balgavy"/><meta name="created" content="2018-04-24 13:00:35 +0000"/><meta name="latitude" content="52.33423205054267"/><meta name="longitude" content="4.867457702591858"/><meta name="source" content="desktop.mac"/><meta name="updated" content="2018-05-25 18:27:30 +0000"/><title>Drawing graphs</title></head><body><div>Embeddings:</div><ul><li><div>circular embedding — vertices are spaced evenly around a circle</div></li><li><div>ranked embedding — choose an arbitrary vertex u, rank other vertices by distance from u, put vertices on separate lines based on ranking</div></li></ul><div><br/></div><div>Planar graphs: graphs where no edges cross</div><ul><li><div>interior region: empty space enclosed by a cycle</div></li><li><div>exterior region: empty space not enclosed by a cycle</div></li><li><div>Euler’s formula for planar graphs:</div></li><ul><li><div>n-m+r=2</div></li><li><div>n vertices, m edges, r regions</div></li></ul><li><div>condition for planar graph: m ≤ 3v-6</div></li><li><div>every planar graph has a vertex <span style="font-style: italic;">v, </span>with δ(<span style="font-style: italic;">v</span>) ≤ 5</div></li></ul><div><br/></div><div><br/></div></body></html>